// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include <unordered_map>
#include "commoncppproblem567.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=567 lang=cpp
 *
 * [567] 字符串的排列
 */

// @lc code=start
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char,int> need,window;
        for(char c : s1)
            need[c]++;

        //
        int right = 0;
        int left = 0;
        int vaild = 0;
        while(right < s2.size())
        {
            //c是有边界字符
            char c = s2[right];

            //右移
            right++;

            //更新右移后的数据
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                {
                    vaild++;
                }
            }

            //判断是否进行窗口左边收缩
            while(right - left >= s1.size())
            {
                //进行判断是否满足条件
                if(vaild == need.size())
                {
                    return true;
                }

                //d是存储左边界的字符
                char d = s2[left];

                //左边窗口缩进
                left++;

                //更新窗口收缩后的数据
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        vaild--;
                    }
                    window[d]--;
                }
            }
        }
        return false;
    }
};
// @lc code=end

